'''
https://leetcode.cn/problems/path-with-minimum-effort/description/
'''
import heapq
from typing import List


class Solution:

    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        # Dijkstra
        distance = [[float('inf')] * n for _ in range(m)]
        distance[0][0] = 0
        visited = [[False] * n for _ in range(m)]

        heap = [(0, 0, 0)]  # 花费0，到0
        while heap:
            cost, x, y = heapq.heappop(heap)
            if not visited[x][y]:
                visited[x][y] = True
                for nx, ny in [(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= nx < m and 0 <= ny < n:
                        n_cost = max(distance[x][y], abs(heights[nx][ny] - heights[x][y]))
                        if not visited[nx][ny] and  n_cost < distance[nx][ny]:
                            distance[nx][ny] = n_cost
                            heapq.heappush(heap, (n_cost, nx, ny))
        return distance[-1][-1]


heights = [[1, 10, 6, 7, 9, 10, 4, 9]]
print(Solution().minimumEffortPath(heights))
